import com.sun.org.apache.bcel.internal.generic.FALOAD;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-25
 * Time: 22:38
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public int pairSum(ListNode head) {
        // 先使用快慢指针找到链表中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 此时 slow 指向中间靠右的那个节点
        // 反转右半部分链表
        ListNode prev = null;
        ListNode cur = slow;
        ListNode next = cur.next;
        // 注意这里的条件是 cur != null
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }
        int ans = Integer.MIN_VALUE;
        // 因为是偶数个节点, 那么最后的终止条件就是, left == null
        // 反转后的链表的头节点是 prev
        while (prev != null) {
            ans = Math.max(ans, prev.val+head.val);
            head = head.next;
            prev = prev.next;
        }
        return ans;
    }
}
